﻿#include <iostream>

static void swap(int* numbers, const int index1, const int index2)
{
    if (index1 == index2) return;

    numbers[index1]=numbers[index1]^numbers[index2];
    numbers[index2]=numbers[index1]^numbers[index2];
    numbers[index1]=numbers[index1]^numbers[index2];
}

static void sort(int* numbers, const size_t size) {
    int targetIndex = 1;
    while (targetIndex < size) {
        for (int i = targetIndex; i > 0; i--) {
            if (numbers[i] < numbers[i - 1]) {
                swap(numbers, i, i - 1);
            }
        }

        targetIndex++;
    }
}

/**
 * 插入排序 [9,0,3,4,1,7,2]
 * 先看前2个数字，9 > 0, 故前两个数字交换位置: [0,9,3,4,1,7,2]
 * 再看前3个数字, 9 > 3, 故第2第3交换位置: [0,3,9,4,1,7,2]
 * 再看前4个数字, 9 > 4, 故第3第4交换位置: [0,3,4,9,1,7,2]
 * 再看前5个数字, 9 > 1, 故第4第5交换位置: [0,3,4,1,9,7,2]
 *              4 > 1, 故第3第4交换位置: [0,3,1,4,9,7,2]
 *              3 > 1, 故第2第3交换位置: [0,1,3,4,9,7,2]
 * 再看前6个数字, 9 > 7, 故第5第6交换位置: [0,1,3,4,7,9,2]
 * 再看前7个数字, 9 > 2, 故第6第7交换位置: [0,1,3,4,7,2,9]
 *              7 > 2, 故第5第6交换位置: [0,1,3,4,2,7,9]
 *              4 > 2, 故第4第5交换位置: [0,1,3,2,4,7,9]
 *              3 > 2, 故第3第4交换位置: [0,1,2,3,4,7,9]
 */
int main_InsertSort()
{
    int arr[] = {9, 100, 32, 50, 47, 81, 7, 1};
    size_t size = sizeof(arr)/sizeof(int);
    sort(arr, size);

    for (int i = 0; i < size; i++) {
        printf("arr[%d]=%d\n", i, arr[i]);
    }

    return 0;
}